package 算法.查找;

import com.sun.org.apache.regexp.internal.recompile;

import util.CompareUtils;
import util.LogUtils;

/**
 * 【BST：二叉查找树】
 * 
 * @author Administrator
 * @Date 2017-09-01
 * @param <K>
 * @param <V>
 * @version TODO:>>>>>>>尚未测试
 */
public class BST<K extends Comparable<K>, V> {
	// BST的根节点
	private Node root;

	private class Node {
		private K k;
		private V v;
		private Node left, right; // 指向左右子树
		private int N; // 以该节点为根的子树中的节点总数

		public Node(K k, V v, int n) {
			this.k = k;
			this.v = v;
			N = n;
		}

		@Override
		public String toString() {
			return "Node [k=" + k + ", v=" + v + ", N=" + N + "]";
		}
	}

	public int size() {
		return size(root);
	}

	/**
	 * 
	 * @param node
	 * @return
	 */
	private int size(Node node) {
		if (node == null)
			return 0;
		return node.N;
	}

	public V get(K targetKey) {
		return get(root, targetKey);
	}

	/**
	 * get方法
	 * 
	 * @param root
	 * @param k
	 * @return
	 */
	public V get(Node root, K k) {
		if (root == null)
			return null;
		int rsCompare = CompareUtils.compareTo(root.k, k);
		if (rsCompare > 0)		return get(root.left, k);
		else if (rsCompare < 0)	return get(root.right, k);
		else					return root.v;
	}

	public void put(K k, V v) {
		root = put(root, k, v);
	}

	/**
	 * put方法：返回返回put后的节点
	 * 
	 * @param root
	 * @param k
	 * @param v
	 * @return
	 */
	public Node put(Node root, K k, V v) {
		if (root == null)		return new Node(k, v, 1);		 // 叶子节点的N为1
		int rsCompare = CompareUtils.compareTo(root.k, k);
		if		(rsCompare > 0) root.left  = put(root.left, k, v);
		else if (rsCompare < 0)	root.right = put(root.right, k, v);
		else					root.v = v; 					// 相同key则val替换
		root.N = size(root.left) + size(root.right) + 1;
		return root;
	}

	public K min() {
		return min(root);
	}

	/**
	 * min：返回最小的Key
	 * 
	 * @param root
	 * @return
	 */
	public K min(Node root) {
		if (root.left == null)	return root.k;
		return min(root.left);
	}

	/**
	 * max：返回最大的Key
	 * 
	 * @param root
	 * @return
	 */
	public K max(Node root) {
		if (root.right == null)	return root.k;
		return max(root.right);
	}

	/**
	 * floor：向下取整
	 * @param targetKey
	 * @return
	 */
	public K floor(K targetKey) {
		Node node = floor(root, targetKey);
		if (node == null)	return null;
		return node.k;
	}

	public Node floor(Node root, K targetKey) {
		if (root == null)
			return null;
		Integer rsCompare = CompareUtils.compareTo(root.k, targetKey);
		
		if (rsCompare == 0)	return root;
		if (rsCompare > 0)	return floor(root.left, targetKey);
		// if (rsCompare < 0)
		Node t = floor(root.right, targetKey);
		if (t != null)	return t;
		return root;
	}

	public void traverse() {
		traverse(root);
	}

	/**
	 * select：找到第n个(排名为第n的)的key
	 * @param n 排名（由0开始计数）
	 * @return  找到的key
	 */
	public K select(int n) {
		Node node = select(root, n);
		if (node == null)	return null;
		return node.k;
	}
	
	public Node select(Node root, int n) {
		if (root == null)	return null;
		int leftSize = size(root.left);
		if (leftSize > n)		return select(root.left, n);
		else if (leftSize < n) 	return select(root.right, n-leftSize-1);
		else 					return root;
	}
	
	/**
	 * rank：返回k在BST中的排名(从0开始计数)
	 * @param k 需要查找排名的key
	 * @return	排名(从0开始)
	 */
	public Integer rank(K k) {
		return rank(root, k);
	}
	
	public Integer rank(Node root, K k) {
		if (root == null)	return 0;
		int rsComp = CompareUtils.compareTo(root.k, k);
		if (rsComp > 0) 
			return rank(root.left, k);
		else if (rsComp < 0) 
			return 1 + size(root.left) +rank(root.right, k);
		else return size(root.left);
	}  
	
	public void deleteMin() {
		root = deleteMin(root);
	}
	
	/**
	 * deleteMin 删除BST中key最小的元素
	 * 				寻找最左的节点
	 * @param root
	 * @return
	 */
	public Node deleteMin(Node root) {
		if(root.left == null)	return root.right;
		root.left = deleteMin(root.left);
		root.N = size(root.left) + size(root.right) + 1;
		return root;
	}
	
	
	public void deleteMax() {
		deleteMax(root);
	}
	
	/**
	 * deleteMax 删除BST中key最大的元素
	 * @param root
	 * @return
	 */
	public Node deleteMax(Node root) {
		if (root.right== null)	return root.left;
		root.right = deleteMax(root.right);
		root.N = size(root.left) + size(root.right) + 1;
		return root;
	}
	
	/**             
	 * 中序遍历
	 */
	public void traverse(Node root) {
		if (root == null) return;
		traverse(root.left);
		LogUtils.println("BST中序遍历", root);
		traverse(root.right);
	}

	public static void main(String[] args) {
		BST<String, Integer> bst = new BST<String, Integer>();
		bst.put("4", 5);
		bst.put("3", 5);
		bst.put("2", 5);
		bst.put("1", 5);
		bst.put("5", 5);
		bst.put("E", 5);
		bst.put("B", 2);
		bst.put("C", 3);
		bst.put("D", 4);
		bst.put("A", 1);
		bst.put("F", 6);
		LogUtils.println("select", bst.select(3));
		bst.traverse();
	}
}
